There are a variety of reasons for detecting crowds of objects such as vehicles, goods, people, animals, etc. For example, this information can be useful for determining traffic information and managing traffic flow (such as determining alternative routes), managing events (such as concerts or emergencies), allocating resources (such as network resources or security or police force) or providing notifications or services relating to the crowds (such as notifications about being in or approaching a crowded location and directions out of or away from the crowded area). This information is also useful to a wide range of service providers, such as telecommunications companies, transportation companies, event planners or government authorities, as well as to drivers or individuals.
Location tracking systems therefore generally refer to systems for determining and tracking the geographic location (e.g., two-dimensional coordinates, such as a longitude and latitude) of objects, for example, in the Global Positioning System (GPS) or the World Geodetic System (WGS). These two-dimensional geographic coordinates can be provided, for example, by GPS-enabled devices, distance sensors, bar code or radio-frequency identification (RFID) scanners.
A crowd refers to the situation in which a square of side length d (d×d) contains a threshold of k or more objects, wherein d and k are selected based on the application. For example, if the reason for detecting the crowds is related to traffic, d could be selected to be relatively large compared to an application for detecting crowds of people. Similarly, if the area is a crowded event center the threshold k could be selected to be larger than, for example, a rural roadway.
Given a total number of objects n, a static determination can be made if there is a crowd by defining the square of side length d around each one of the tracked objects n and then solving the problem of determining whether there exists a union of k or more of the squares. Generally, the problem of determining a length of the union of n intervals is referred to as Klee's measure problem.
In 1977, Jon Bentley proposed an algorithm which is still used today as a solution to Klee's measure problem for two-dimensional rectangular ranges. This solution, known as Bentley's algorithm or a sweep-line approach, because the solution is determined by sweeping a line across the area of union rather than reconstructing the union itself, relies on the use of a segment tree to store individual 1-dimensional distances of the lines. Segment trees are well-known in the art of computer science, and more particularly in the art of computational geometry, as a way for efficiently storing and retrieving a data set of n intervals (i.e., the number of total objects) and require an amount of storage corresponding to n log n and a computational runtime of O(n log n)—the runtime for each insertion or deletion in a segment tree is log n, and therefore n insertions/deletions take n log n runtime.
When the static solution described above is used in location tracking systems, however, in which crowds are detected and tracked with respect to time, and typically in real time, the storage and runtime required increases quadratically (i.e., by a power of 2) with the total number of objects n being tracked. This is because each of the objects n sends updates with a frequency f updates per minute. Therefore, using the sweep-line approach, crowd detection in a location tracking system requires the static solution n log n to be performed n times with frequency f(f×n×n log n=f n2 log n), thereby increasing the required amount of storage and computational runtime quadratically with the total number of objects n being tracked.
Accordingly, when there are a large total number of objects n being tracked (as is becoming more and more so the case in location tracking systems), the sweep-line approach is not suitable in that its use would be expensive and burdensome with respect to hardware requirements, as well as slow and cumbersome. For example, in order to be used in a location tracking system that is configured to track a total number of objects n on the order of up to tens of millions of objects, each providing a location update on average about once per second, the sweep-line approach would require an amount of hardware sufficient to process about 1012 operations per second, and therefore would require a very complex and expensive computer system.